The present invention relates to correction of one or more symbols in error in a sequence of symbols. More specifically, it relates to error correction by first identifying the location of possible errors, followed by reconstruction of the original symbols from the remaining symbols believed to be not in error.
Error correction of symbols is well known, especially in the field of communications and information storage or transfer. In general, a series of symbols that is being transferred may have experienced interference or noise on a transmission channel. Possibly the storage medium, such as an optical or magnetic disk, may have been damaged. As a consequence, a received sequence of symbols may be different from the sequence from which it originated. The difference between an original sequence of symbols and a received sequence may be considered to be errors.
Error control measures can be applied to detect and to correct errors. These measures in general comprise adding additional symbols to a sequence, based on the existing symbols in the original sequence. The redundancy of symbols allows for detection and sometimes correction of errors.
It usually requires a greater number of redundant symbols to correct errors rather than to merely detect that symbols are in errors. For instance, in data communications, wherein re-sending of information is possible and not detrimental to the quality of data transfer, it may be sufficient to detect errors and request the transmitter to resend the symbols. However, in many applications resending of symbols is impossible or undesirable. In such cases error correction is desirable.
Error-correction techniques for symbols in a sequence attempt to achieve the best result with as few redundant symbols as possible, and with as limited processing requirements and memory or storage requirements as possible. Error correcting redundancy is usually set to address some maximum or optimal expected symbol error ratio. If information is coded into codewords, it is to be expected that many codewords are error-free and in error-free codewords extra symbols provided for error correction or detection are truly redundant.
Effective error correcting codes with a possibility to correct a limited number of symbols in a sequence of a greater number of symbols require significant processing and/or memory capabilities. Maximum likelihood error correction may also require significant memory or storage capabilities. Accordingly, novel and improved methods and apparatus providing improved error correcting performance with limited symbol redundancy and limited processing resources are required.